/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package quicksort;

import java.util.Scanner;

/**
 *
 * @author Eddie
 */
public class Quicksort {

    static int comparisons;
    static int arrayCalls;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {



        int inputSize = (int) (Math.random()*100);
        int input[] = new int[inputSize];
        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < inputSize; i++) {
            input[i] = (int)(Math.random()*100);
        }

        quicksort(input, 0, inputSize - 1);

        for (int i = 0; i < inputSize; i++) {
            System.out.print(input[i] + " ");
        }
        System.out.println("");
        System.out.println("Array Calls:" + arrayCalls);
        System.out.println("Comparisons: " + comparisons);



    }

    static int partition(int input[], int start, int end) {

        int pivot = getValue(input, start);
        while (compare(start, '<', end)) {

            while (compare(getValue(input, start), '<', pivot)) {
                start++;
            }

            while (compare(getValue(input, end), '>', pivot)) {
                end--;
            }

            if (compare(getValue(input, start), '=', getValue(input, end))) {
                end--;

            } else if (compare(start, '<', end)) {
                int temp = input[start];
                input[start] = input[end];
                input[end] = temp;
                arrayCalls+=4;

            }

        }

        return start;
    }

    static void quicksort(int input[], int start, int end) {
        if (compare(start, '<', end)) {
            int middle = partition(input, start, end);
            quicksort(input, start, middle - 1);
            quicksort(input, middle + 1, end);
        }
    }

    static boolean compare(int x, char c, int y) {
        comparisons++;
        if (c == '<') {
            if (x < y) {
                return true;
            } else {
                return false;
            }
        } else if (c == '=') {
            if (x == y) {
                return true;
            } else {
                return false;
            }
        } else if (c == '>') {
            if (x > y) {
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }
    
    static int getValue(int input[], int location){
        arrayCalls++;
        return input[location];
    }
}
